/*
用邻接表存储有向图G，具有n个顶点，其值分别为从1到n，试设计一个算法，输出该有向图G中从顶点u到v的所有简单路径。

输入：
首先输入无向图的顶点个数n和边的数目m
输入n个顶点，顶点之间用空格分开
输入m条边
输入u，v

输出：
从u到v的简单路径，一行输入一个路径

输入：
4 6
1 2 3 4
1 2
1 3
1 4
2 3
2 4
3 4
1 4
输出：
1 4
1 3 4
1 2 4
1 2 3 4
*/

#include <iostream>
#include <queue>
using namespace std;
#define MVNum 1000//最大顶点数
int visited[MVNum]={0};//判别顶点是否被访问过
int path[MVNum];
typedef struct ArcNode//边结点
{
    int adjvex; //该边所指向的顶点的位置
    struct ArcNode *nextarc; //指向下一条边的指针
    //OtheInfo info;//边相关的信息（如权值）
}ArcNode;

typedef struct VNode//顶点信息
{ 
    int data;
    ArcNode *firstarc; //指向第一条依附该顶点的边的指针
}VNode, AdjList[MVNum];//AdjList表示邻接表类型为VNode型数组

typedef struct//邻接表
{
    AdjList adjlist;
    int vexnum, arcnum; //图的当前顶点数和边数
}ALG;//邻接表

int LocateVex(ALG G, int v)//邻接表G中v的位置
{
    for(int i=1; i<=G.vexnum; i++)
    {
        if(G.adjlist[i].data == v)
           return i;
    }
    return -1;
}

void CreateDG(ALG &G)//邻接表表示法，创建 有向图G
{
    int i, j, k, temp;
    cin >> G.vexnum >> G.arcnum;//输入图总顶点数和总边数
    for (i = 1; i <= G.vexnum; i++) // 输入各点，构建 邻接表头结点表,从1开始编号
    {
        cin >> temp;
        G.adjlist[i].data = temp;
        G.adjlist[i].firstarc = NULL; //指向第一条依附该顶点的边的指针,初始化为NULL
    }
    for (k = 0; k < G.arcnum; k++) // 输入各边，构建邻接表
    {
        int v1, v2;
        //char ch;
        cin >> v1 >> v2; // 输入一条边的两个顶点
        // scanf("%d%c%d",&v1,&ch,&v2);
        i = LocateVex(G, v1);//确定v1和v2在G中位置i和j，即顶点在G.adjlist中的序号
        j = LocateVex(G, v2);
        ArcNode *p;
        p=new ArcNode;//生成一个新的边结点
        p->adjvex = j;//该边所指向的顶点的位置为j，即该边的邻接点序号为j
        p->nextarc = G.adjlist[i].firstarc;
        G.adjlist[i].firstarc = p;//头插法，把新的边结点插入插入顶点Vi的 邻接边表 的头部
    }
}

void prtpath(int d)
{
    int i;
    for (i = 0; i < d;i++)
    {
        cout << path[i] << ' ';
    }
    cout << endl;
}

void DFSAL(ALG G,int u,int v,int d)//深度优先遍历 邻接表 储存的图，从第v个顶点开始
{
    ArcNode *p;
    visited[u] = 1;//走到顶点u，标记u
    path[d] = u;
    d++;//路径长度+1
    if(u==v)//找到一条路径了，马上输出
    {
        prtpath(d);
    }
    else
    {
        p = G.adjlist[u].firstarc; // p为第v个顶点的第一条邻接边
        while (p != NULL)
        {
           if (visited[p->adjvex] == 0) // p->adjvex为第v个顶点的第一条邻接边指向的顶点，即第v个顶点相邻顶点的位置。没有被访问
           {
               DFSAL(G, p->adjvex, v, d); // 递归遍历
           }
           p = p->nextarc; // p移到下一个边结点
        }
    }
    visited[u] = 0;//回溯，清除访问信息
    //cout << "@" << u << ' ' << d << endl;
}

void coutAL(ALG G,int v)//输出 邻接表 储存的图，从第v个顶点开始
{
    int i;
    ArcNode *p;
    for (i = v; i <= G.vexnum; i++)
    {
        cout << G.adjlist[i].data << ':';  // 输出被访问顶点
        p = G.adjlist[i].firstarc;        // 与第i个顶点邻接的第一条边
        while (p != NULL)
        {
           cout << G.adjlist[p->adjvex].data << ' '; // 输出被访问顶点
           p = p->nextarc;//下一个边结点，找下一个结点
        }
        cout << endl;
    }
}

int main()
{
    ALG G;
    int u, v;
    CreateDG(G);
    cin >> u >> v;
    //coutAL(G, u);
    DFSAL(G, u, v, 0);
    return 0;
}